package cn.suchan.jianzhi.q36_link;

import java.util.Stack;

/**
 * 知识点：两个链表的一个公共节点
 * 题目描述
 * 输入两个链表，找出它们的第一个公共结点。
 * （当链表中出现公共节点后，该公共节点后面的节点都是相同的。
 * 例如：
 * #       1→2→3
 * #               ↘
 * #                 4→5→6→7→8
 * #               ↗
 * #  9→10→11→12
 * ）
 *
 * @author suchan
 * @date 2019/06/02
 */
public class Solution {

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode tempNode1 = pHead1;
        ListNode tempNode2 = pHead2;

        while (tempNode1 != null) {
            while (tempNode2 != null) {
                if (tempNode1 == tempNode2) {
                    return tempNode2;
                }
                tempNode2 = tempNode2.next;
            }
            tempNode2 = pHead2;
            tempNode1 = tempNode1.next;
        }
        return null;
    }

    /**
     * 借助栈来实现(比上面那个效率高点)
     *
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        Stack<ListNode> stack1 = new Stack();
        Stack<ListNode> stack2 = new Stack();

        ListNode tempNode1 = pHead1;
        while (tempNode1 != null) {
            stack1.push(tempNode1);
            tempNode1 = tempNode1.next;
        }

        ListNode tempNode2 = pHead2;
        while (tempNode2 != null) {
            stack2.push(tempNode2);
            tempNode2 = tempNode2.next;
        }

        ListNode common = null;
        while (!stack1.empty() && !stack2.empty()) {
            System.out.println("stack1.peek()==>" + stack1.peek().val + " & stack2.peek()==>" + stack2.peek().val);
            if (stack1.peek() == stack2.peek()) {
                common = stack1.pop();
                stack2.pop();
            } else {
                break;
            }
        }
        return common;
    }

    /**
     * @param head1
     * @param head2
     * @return
     */
    public ListNode FindFirstCommonNode2(ListNode head1, ListNode head2) {
        // 得到两个链表的长度
        int length1 = getListLength(head1);
        int length2 = getListLength(head2);
        int diff = length1 - length2;
        System.out.println("length1==>" + length1 + "  length2==>" + length2 + "  diff==>" + diff);
        System.out.println("=======================");

        // 先默认head1是长的，head2是短的
        ListNode headLong = head1;
        ListNode headShort = head2;
        // 如果diff小于零，再进行转换
        if (diff < 0) {
            headLong = head2;
            headShort = head1;
            diff = length2 - length1;
        }
        System.out.println("headLong.val==>" + headLong.val);
        System.out.println("=======================");
        // 先在长链表上走几步
        for (int i = 0; i < diff; i++) {
            headLong = headLong.next;
            System.out.println("headLong.val==>" + headLong.val);
        }
        // 再同时在两个链表上遍历
        ListNode commonNode = null;
        while (headLong != null && headShort != null) {
            if (headLong == headShort) {
                commonNode = headLong;
                break;
            }
            headLong = headLong.next;
            headShort = headShort.next;
        }
        return commonNode;
    }

    private int getListLength(ListNode head) {
        int length = 0;
        ListNode tempNode = head;
        while (tempNode != null) {
            tempNode = tempNode.next;
            length++;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(0);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode8 = new ListNode(8);
        ListNode listNode9 = new ListNode(9);
        listNode.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode8;
        listNode8.next = listNode9;

        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);

        listNode4.next = listNode5;
        listNode5.next = listNode6;
        listNode6.next = listNode8;

        Solution solution = new Solution();
        ListNode listNode7 = solution.FindFirstCommonNode1(listNode, listNode4);
        if (listNode7 != null) {
            System.out.println(listNode7.val);
        } else {
            System.out.println("null");
        }
    }
}
